# 32/100 链表-随机链表的复制
# leetcode第138题: https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/2
from typing import Optional
from leetcode.bds import ListNode, ListConvert
from leetcode.test import test_function as tf


class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

    def __str__(self):
        return str(self.val)


def copyRandomList(head: 'Optional[Node]') -> 'Optional[Node]':
    """我的方法, 通过一个新旧节点链表的映射来进行深拷贝"""

    if not head:
        return None

    curr = head
    res_head = res_curr = Node(0)
    mapping = {}  # 一个原链表的节点地址对应新链表节点地址的映射
    while curr:
        res_curr.val, res_curr.next = curr.val, Node(0)
        mapping[curr] = res_curr
        # 指针后移
        res_curr, curr = res_curr.next, curr.next

    res_curr, curr = res_head, head
    while curr:
        if curr.random:
            res_curr.random = mapping[curr.random]
        if curr.next:
            curr, res_curr = curr.next, res_curr.next
        else:  # 删除多余的尾结点
            curr = curr.next
            res_curr.next = None

    return res_head


def copyRandomList_opt(head: 'Optional[Node]') -> 'Optional[Node]':
    if not head:
        return None

    mapping = {}
    cur = head
    while cur:
        mapping[cur] = Node(cur.val)
        cur = cur.next
    cur = head
    while cur:
        mapping[cur].next = mapping.get(cur.next)
        mapping[cur].random = mapping.get(cur.random)
        cur = cur.next
    return mapping[head]


if __name__ == '__main__':
    head1 = Node(7, None, None)
    n11 = Node(13, None, None)
    n12 = Node(11, None, None)
    n13 = Node(10, None, None)
    n14 = Node(1, None, None)
    head1.next, head1.random = n11, None
    n11.next, n11.random = n12, head1
    n12.next, n12.random = n13, n14
    n13.next, n13.random = n14, n12
    n14.next, n14.random = None, head1

    head2 = Node(1)
    n21 = Node(2)
    head2.next, head2.random = n21, n21
    n21.next, n21.random = None, n21

    head3 = Node(3)
    n31 = Node(3)
    n32 = Node(3)
    head3.next, head3.random = n31, None
    n31.next, n31.random = n32, head3
    n32.next, n32.random = None, None

    copyRandomList(head1)
